package com.demo.algorithms.sort;

import java.util.Arrays;
import java.util.Random;

/**
 * 快速排序：
 * 排序效率在同为O(N*logN)的几种排序方法中效率较高。
 * <p>
 * 1．先从数列中取出一个数作为基准数。
 * 2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
 * 3．再对左右区间重复第二步，直到各区间只有一个数。
 *
 * @author: 蔡奇峰
 * @date: 2020/7/22 下午2:36
 */
public class QuickSort {

    public static void main(String[] args) {
//        int[] arr = {-1, 22, 66, -10, 17, 18, 46, 36, 28};

        int[] arr = new int[67780];
        for (int i = 0; i < 67780; i++) {

            arr[i] = new Random().nextInt(18060);
        }

        System.out.println("数组排序前：" + Arrays.toString(arr));

        long timeMillis = System.currentTimeMillis();
//        Arrays.sort(arr);
        sort(arr, 0, arr.length - 1);
        long timeMilli = System.currentTimeMillis();

        System.out.println("数组排序后：" + Arrays.toString(arr));

        System.out.println("插入排序耗时：" + (timeMilli - timeMillis));
    }


    /**
     * 快速排序
     * 分成两组,和中间值进行比较,小的放左边,大的放右边;
     *
     *
     * @param arr 需要排序的数组
     * @param paramLeft   左边的下标,从最左边开始
     * @param paramRight   右边的下标,从最右边开始
     */
    public static void sort(int[] arr, int paramLeft, int paramRight) {
        // 左边下标
        int left = paramLeft;
        // 右边下标
        int right = paramRight;
        // 基准（这里以中间值作为基准）, TODO 注意：不能用数组的长度,否则得到的不是中间值
        int middle = arr[(paramLeft + paramRight) / 2];
        // 临时变量,用于辅助交换
        int temp;

        // 和中间值进行小的放左边，大的放右边
        while (left < right) {

            // 从左边开始遍历,小于中间值则放左边
            while (arr[left] < middle) {
                left += 1;
            }
            // 从右边开始遍历，大于中间值则放右边
            while (arr[right] > middle) {
                right -= 1;
            }
            // 左边下标 >= 右边下标则比较结束
            if (left >= right) {
                break;
            }
            // 交换,整个方法只有这里进行了排序.
            temp = arr[right];
            arr[right] = arr[left];
            arr[left] = temp;

            // 如果左边和中间值相等,则右边下标左移
            if (arr[left] == middle) {
                right -= 1;
            }
            // 如果右边和中间值相等，则左边下标右移
            if (arr[right] == middle) {
                left += 1;
            }
        }
        // 如果相等则继续移动,避免栈溢出
        if (right == left) {
            left += 1;
            right -= 1;
        }

        // 向左边递归
        if (paramLeft < right) {
            sort(arr, paramLeft, right);
        }
        // 向右边递归
        if (paramRight > left) {
            sort(arr, left, paramRight);
        }

    }

}
